package com.test.demo.algorithm.sort;

public class ShellSort {
    /**
     * 希尔排序：将数组进行分组，每次除以二，直到最后为一组。网上的版本
     * 7s
     *
     * @param array
     * @return
     */
    public static int[] shellSort(int[] array) {
        //对元素进行分组
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            //从分组的
            for (int i = gap; i < array.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (array[j] > array[j + gap]) {
                        int temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }
            }
        }

        return array;
    }

    /**
     * 希尔排序（缩小增量排序）：对元素进行分组，按照数组的长度，每次除以2直到为一组，对每组进行插入排序，插入排序的特点就是本身越顺序，速度越快
     * 在插入排序中如最后面有非常小的值，那么移动次数接近N，如果通过分组则可以避免这种情况，提前将小的值排到前面
     * 12ms
     *
     * @param array
     * @return
     */
    public static int[] shellSort2(int[] array) {
        //对元素进行分组
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            //遍历每个分组的内容
            for (int i = 0; i <= gap; i++) {
                //将每组进行插入排序
                for (int j = gap + i; j < array.length; j += gap) {
                    //每次跨度是gap
                    int insertValue = array[j];
                    int insertindex = j;
                    //假设每组的前面都是排好序的，第index-gap比要插入的数要小就要往后挪动gap个位置，依次递减gap继续比较
                    while (insertindex >= gap && array[insertindex - gap] > insertValue) {
                        array[insertindex] = array[insertindex - gap];
                        insertindex -= gap;
                    }
                    array[insertindex] = insertValue;
                }
            }
        }
        return array;
    }
}
